package fun.coding.leetcode;

public class MergeSortedArray {

	/**
	 * Given two sorted integer arrays A and B, merge B into A as one sorted array.
	 */
	// Has to be an in-place algorithm, and make use of that assumption that 
	// You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B.
	// My original thought is way too complicated, just reverse the thought and find the max of these two arrays
	// And start populating from the end. So smart!
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println("Done");
	}
	
	public void merge(int A[], int m, int B[], int n) {
		if (!(A != null && B != null)) {
			return;
		}
		
		int i = m - 1;
		int j = n - 1;
		int k = m + n - 1;
		
		while (i >= 0 && j >= 0) {
			if (A[i] > B[j]) {
				A[k] = A[i];
				i--;
			} else {
				A[k] = B[j];
				j--;
			}
			
			k--;
		}
		
		while (j >= 0) {
			A[k] = B[j];
			k--;
			j--;
		}
	}
	

}
